package tree

//给定一个非空二叉树，返回其最大路径和
//路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点

type ResultType struct {
	SinglePath int // 保存单边最大值
	MaxPath    int //保存最大值(单边或者两个单边+root值)
}

func MaxPathSum(root *Node) int {
	result := helper(root)
	return result.MaxPath
}
func helper(root *Node) ResultType {
	//check
	if root == nil {
		return ResultType{
			SinglePath: 0,
			MaxPath:    -(1 << 31),
		}
	}

	//divide
	left := helper(root.Left)
	right := helper(root.Right)

	//conquer
	result := ResultType{}
	if left.SinglePath > right.SinglePath {
		result.SinglePath = max(left.SinglePath+root.Val, 0)
	} else {
		result.SinglePath = max(right.SinglePath+root.Val, 0)
	}

	//求两边加根节点的最大值
	maxPath := max(left.MaxPath, right.MaxPath)
	result.MaxPath = max(maxPath, left.SinglePath+right.SinglePath+root.Val)
	return result

}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
